package lanqiao._02算法训练.page02;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 问题描述
 * 　　George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
 * 输入格式
 * 　　The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
 * 输出格式
 * 　　The output should contains the smallest possible length of original sticks, one per line.
 * 样例输入
 * 9
 * 5 2 1 5 2 1 5 2 1
 * 4
 * 1 2 3 4
 * 0
 * 样例输出
 * 6
 * 5
 * 思路：
 * max = max(nums), sum = sum(nums)
 * 原先最小的长度target >= max, 并且可以整除 sum
 * 从target 到 sum dfs 判断是否可行
 * dfs 将所有木棍拼接成若干个 target:
 * 先排序，方便剪枝
 * @since 2022 - 11 - 04 - 23:20
 */
public class _15sticks {
}

class Main15 {
    static int[] nums = new int[64];
    static boolean[] vis = new boolean[64];
    static boolean find = false;    //是否找到的标识
    static int len;     //木棍个数
    static int target;  //目标长度

    /**
     * @param time   已使用木棍的个数
     * @param curLen 当前拼接的木棍长度
     * @param index  当前准备使用的木棍下标 初始为 len - 1
     */
    static void dfs(int time, int curLen, int index) {
        if (find) return;
        if (curLen == 0) {    //在剩余木棍中取一个
            int i = len - 1;
            while (vis[i]) i--;
            vis[i] = true;
            dfs(time + 1, nums[i], i - 1);
            vis[i] = false;
//            if(find) return;
            //失败
            return;
        }

        if (curLen == target) {   //拼出一个target长的木棍
            //每个木棍都访问过了
            if (time == len) find = true;
            else {   //继续尝试从剩余木棍中拼出target长的
                dfs(time, 0, index);    //第三个参数无用
                if (find) return;
            }
            return;
        }
        //数组从小到大排序，倒着访问就是从大到小
        //拼接木棍
        for (int i = index; i >= 0; i--) {
            if (!vis[i] && curLen + nums[i] <= target) {
                //剪枝：上一个相同的木棍没有使用，使用这根也无法得到预期结果
                if (i < len - 1 && !vis[i + 1] && nums[i] == nums[i + 1]) {
                    continue;
                }
                vis[i] = true;
                dfs(time + 1, curLen + nums[i], i - 1);
                if (find) return;
                vis[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        while ((n = sc.nextInt()) != 0) {
            int max = -1, sum = 0;
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
                sum += nums[i];
                max = Math.max(max, nums[i]);
            }
            len = n;
            //排序 方便剪枝
            Arrays.sort(nums, 0, n);
            //原先最小的长度 >= max, 并且可以整除 sum
            for (int i = max; i <= sum / 2; i++) {
                if (sum % i != 0) continue;
                //dfs 检测是否可以拼接成若干个 target
                target = i;
                find = false;
                for (int j = 0; j < n; j++) vis[j] = false;
                dfs(0, 0, len - 1);
                if (find) {
                    System.out.println(i);
                    break;
                }
            }
            if (!find) {
                System.out.println(sum);
            }
        }
    }
}

//超时
class Main15_1 {
    static int[] nums = new int[64];
    static boolean[] vis = new boolean[64];
    static boolean find = false;

    static void dfs(int time, int len, int target) {
        //最多操作len次
        if (time >= len || find) return;
        if (check(len, target)) { //检查是否满足
            find = true;
            return;
        }
        for (int i = 0; i < len; i++) {
            //在剩下的木棍中选一个
            if (!vis[i]) {
                vis[i] = true;
                if (nums[i] < target) {
                    //沾到另外剩余的木棍上
                    for (int j = 0; j < len; j++) {
                        if (!vis[j] && i != j) {
                            if (nums[i] + nums[j] <= target) {
                                nums[j] += nums[i];
                                dfs(i + 1, len, target);
                                nums[j] -= nums[i];
                            }
                        }
                    }
                } else if (nums[i] == target) {    //当前木棍为目标长度，保留
                    dfs(i + 1, len, target);
                }
                vis[i] = false;
            }
        }

    }

    private static boolean check(int len, int target) {
        for (int i = 0; i < len; i++) {
            if (!vis[i]) {    //剩下的木棍
                if (nums[i] != target) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        while ((n = sc.nextInt()) != 0) {
            int max = -1;
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
                max = Math.max(max, nums[i]);
            }
            find = false;
            int t = max;
            while (true) {
                for (int i = 0; i < 64; i++) vis[i] = false;
                dfs(0, n, t);
                if (find)
                    break;
                t++;
            }
            System.out.println(t);
        }
    }
}